from typing import List

# 螺旋矩阵Ⅱ
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 方向向量
        matrix = [[0] * n for _ in range(n)]  # 初始化零矩阵
        row, col = 0, 0  # 当前位置坐标，初始 (0, 0)
        dirIdx = 0  # 当前方向索引（0-3 分别对应四个方向）
        for i in range(n * n):
            matrix[row][col] = i + 1
            dx, dy = dirs[dirIdx]
            r, c = row + dx, col + dy  # 计算下一个位置(r, c)，当前位置加上方向向量

            # 若下一步的位置超出矩阵边界，或者是之前访问过的位置
            if r < 0 or r >= n or c < 0 or c >= n or matrix[r][c] > 0:
                dirIdx = (dirIdx + 1) % 4  # 顺时针旋转至下一个方向，0→1→2→3→0
                dx, dy = dirs[dirIdx]  # 获取新方向

            row, col = row + dx, col + dy

        return matrix

s = Solution()
print(s.generateMatrix(3))